import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {

    List<String> ret=new ArrayList<>();
    StringBuilder s =new StringBuilder();
    public List<String> letterCombinations(String digits) {
        String[] arr={"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        if(digits.equals("")) return ret;

        dfs(digits,arr,0);
        Math.max(1,2);

        return ret;
    }

    private void dfs(String digits,String[] arr,int pos){
        if(pos==digits.length()){

            ret.add(s.toString());
            return;
        }

        char[] ss=arr[digits.charAt(pos)-'0'-2].toCharArray();


        for(int i=0;i<ss.length;i++){

            s.append(ss[i]);
            dfs(digits,arr,pos+1);
            s.deleteCharAt(s.length()-1);


        }
    }
}


class Solution1 {
    List<List<Integer>> ret;
    List<Integer> list;
    boolean[] vis;

    public List<List<Integer>> permuteUnique(int[] nums) {
        ret=new ArrayList<>();
        list=new ArrayList<>();
        int n=nums.length;

        vis=new boolean[n];
        Arrays.sort(nums);

        dfs(nums,0);

        return ret;
    }

    private void dfs(int[] nums,int pos){
        if(pos==nums.length){
            ret.add(new ArrayList(list));
            return;
        }

        for(int i=0;i<nums.length;i++){
            if(vis[i]||i>0&&nums[i]==nums[i-1]&&!vis[i-1]) continue;

            list.add(nums[i]);
            vis[i]=true;
            dfs(nums,pos+1);

            vis[i]=false;
            list.remove(list.size()-1);
        }
    }
}



class Solution2 {
    int count1=0;
    int count2=0;

    StringBuilder s=new StringBuilder();
    List<String> ret=new ArrayList<>();

    public List<String> generateParenthesis(int n) {


        dfs(n,0);
        return ret;
    }


    private void dfs(int n,int pos){
        if(pos==n*2){
            ret.add(s.toString());
            return;
        }

        if(count1==n){
            s.append(')');
            count2++;
            dfs(n,pos+1);
            count2--;

            s.deleteCharAt(s.length()-1);
        }else if(count1>count2){
            s.append('(');
            count1++;
            dfs(n,pos+1);

            s.deleteCharAt(s.length()-1);
            count1--;

            s.append(')');
            count2++;
            dfs(n,pos+1);

            count2--;
            s.deleteCharAt(s.length()-1);
        }else if(count1==count2){
            s.append('(');
            count1++;
            dfs(n,pos+1);

            count1--;

            s.deleteCharAt(s.length()-1);
        }



    }
}



class Solution3 {
    List<List<Integer>> ret=new ArrayList<>();
    List<Integer> list=new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {

        dfs(n,k,1);
        return ret;

    }

    private void dfs(int n,int k,int i){
        if(list.size()==k){
            ret.add(new ArrayList(list));
            return;
        }

        for(;i<=n;i++){

            list.add(i);

            dfs(n,k,i+1);

            list.remove(list.size()-1);



        }

    }
}



//目标和递归方法
class Solution4{
    int ret=0;

    public int findTargetSumWays(int[] nums, int target) {
        dfs(nums,target,0,0);
        return ret;
    }

    private void dfs(int[] nums,int target,int num,int pos){

        if(pos==nums.length){
            if(num==target) ret++;
            return;
        }
        dfs(nums,target,num+nums[pos],pos+1);
        dfs(nums,target,num-nums[pos],pos+1);


    }
}



//目标和动态规划解法

class Solution5 {
    public int findTargetSumWays(int[] nums, int target) {
        int sum=0;


        for(int num:nums) sum+=num;

        if((sum+target)%2!=0) return 0;
        int k=(sum+target)/2;
        if(k<0){
            k=(sum-target)/2;
        }

        int[] dp=new int[k+1];
        dp[0]=1;

        for(int j=0;j<nums.length;j++)
            for(int i=k;i>=0;i--){
                if(i-nums[j]>=0) dp[i]+=dp[i-nums[j]];

            }

        return dp[k];
    }
}